#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
#include "linkqueue.h"

//创建二叉树 
bitree tree_create(){
    data_t ch;
    bitree r;
   
    scanf("%c", &ch);
    if(ch == '#')
	return NULL;

    r = (bitree)malloc(sizeof(bitnode));
    if (r == NULL) {
	printf("malloc failed\n");
	return NULL;
    }

    r->data = ch;
    r->left = tree_create();
    r->right = tree_create();
    return r;
}

//先序遍历(根左右)
void preorder(bitree r){
    if (r == NULL)
	return;

    printf("%c", r->data);
    preorder(r->left);
    preorder(r->right);
}
//中序遍历(左根右)
void inorder(bitree r){
    if (r == NULL)
	return;

    inorder(r->left);
    printf("%c", r->data);
    inorder(r->right);
}

//后序遍历(左右根)
void postorder(bitree r){
    if (r == NULL)
	return;

    postorder(r->left);
    postorder(r->right);
    printf("%c", r->data);
}


//层次遍历
void layerorder(bitree r){
    if (r == NULL)
	return;

    linkqueue lq =queue_create();
    if (lq == NULL)
	return;

    printf("%c",r->data);
    enqueue(lq,r);

    while (!queue_empty(lq)) {
	r = dequeue(lq);
	if (r->left) {
	    printf("%c", r->left->data);
	    enqueue(lq, r->left);
	}
	if (r->right) {
	    printf("%c", r->right->data);
	    enqueue(lq, r->right);
	}
    
    }
    puts("");
}
